# Lower Bound

• 2026년 6월 25일 알고리즘
  분할 정복 — 나누어 풀고, 정렬의 한계를 증명하다

  분할 정복은 문제를 나눠 풀고 합치는 전략이다. merge sort의 점화식을 대입법으로 풀어 O(n log n)을 유도하고, 메모리 약점과 대안 heap sort를 본다. 비교 기반 정렬이 Ω(n log n)보다 빠를 수 없음을 결정 트리로 증명한다.